using std::cout;

/* --------------------------------------
   The Node Class Declaration
-------------------------------------- */
class node {
	public:
		int value;						// the value
		node* left;						// left son pointer
		node* right;					// right son pointer
		//node* next;					// next node in LIST
		//node* prev;					// previous node in da LIST
		node** lst;						// pointer2pointer
	
		node( int );					// init
		node* insert( int );			// insert INT
		int max( void );				// max value of subtree
		int min( void );				// min value of subtree
		node* deletemin( void );		// remove min node
		void list_remove( void );		//
		node** lfind( int );			// get list pointer
		
		// just-a-bitches:
		void debug_print( int, int );	// print a tree based on current node
		void debug_dfs( void );			// print DFS
	
	//private:
		void ins( node* );				// insert a node
};

/* --------------------------------------
   not-a-lego constructor
-------------------------------------- */
node::node( int t ) {
	this->value	= t;
	this->left	= NULL;
	this->right	= NULL;
	this->lst = NULL;
}

/* --------------------------------------
   Find Maximum Value, lol
-------------------------------------- */
int node::max( void ) {
	if( this->right )
		return this->right->max();
	else
		return this->value;
}

/* --------------------------------------
   Find Minimum Value
-------------------------------------- */
int node::min( void ) {
	if( this->left )
		return this->left->min();
	else
		return this->value;
}

/* --------------------------------------
   Insert Integer
-------------------------------------- */
node* node::insert( int g ) {
	node* x = new node( g );
	this->ins( x );
	return x;
}


/* --------------------------------------
   Get Pointer in tha List
-------------------------------------- */
node** node::lfind( int a ) {
	if( this->value == a )
		return this->lst;
	if( this->value < a )
		if( this->right )
			return this->right->lfind( a );
	else
		if( this->left )
			return this->left->lfind( a );
	return NULL;
}

/* --------------------------------------
   Insert the Struct
-------------------------------------- */
void node::ins( node* t ) {
	node* tmp;
	if( t->value < this->value ) {
		if( !this->left )
			this->left = t;
		else
			//if( this->value-1 == t->value )
			#if SIMPLE_INS
			if( this->left->value < t->value ) {
			#else
			if( this->left->max() < t->value ) {
			#endif
				if( !this->left->right ) {
					this->left->right = t;
					return;
				}
				tmp = this->left;
				this->left = t;
				this->ins( tmp );
			}
			else
				this->left->ins( t );
	}
	else {
		if( !this->right )
			this->right = t;
		else
			#if SIMPLE_INS
			if( this->right->value < t->value ) {
			#else
			if( this->right->max() < t->value ) {
			#endif
				if( !this->right->right ) {
					this->right->right = t;
					return;
				}
				tmp = this->right;
				this->right = t;
				this->ins( tmp );
			}
			else
				this->right->ins( t );
	}	
}

/* --------------------------------------
   Delete Minimal
-------------------------------------- */
node* node::deletemin( void ) {
	node* tmp = NULL;
	if( !this->left ) {
		//cout << this->value;
		if( this->right ) {
			tmp = this->right;
			#if DEBUG_MODE
				debug( "delete_without_left_but_with_right" );
			#endif
		}
		#if DEBUG_MODE
		else
			debug("delete_without_left_and_right");
		#endif
		//*this->id = NULL;
		//this->lst->remove();
		this->list_remove( );
		delete this;
		return tmp;
	}
	tmp = this->left->deletemin();
	this->left = tmp;
	//cout << this->value;
	#if DEBUG_MODE
		debug( "left_set_to_TMP", 0 );
	#endif
	return this;
}

/* --------------------------------------
   Debug DFS
-------------------------------------- */
void node::debug_dfs( void ) {
	if( this->left )
		this->left->debug_dfs();
	cout << this->value << ' ';
	if( this->right )
		this->right->debug_dfs();
}

/* --------------------------------------
   Debug Console Print
-------------------------------------- */
void node::debug_print( int lev, int x ) {

	gotoxy( x, lev );
	printf( "%d", this->value );
	#if DEBUG_MODE
		if( lev > DBG_MAXLEV )
			error( "Too many levels" );
		if( this->value > DBG_LIMIT || this->value < -1*DBG_LIMIT )
			error( "Limit reached" );
	#endif

	if( this->left )
		this->left->debug_print(  lev+1, x-(x>>(lev+1)) );
	if( this->right )
		this->right->debug_print( lev+1, x+(x>>(lev+1)) );
}


/* --------------------------------------
   Remove From the list
-------------------------------------- */
void node::list_remove( void ) {
	#if DEBUG_MODE == 1
		debug( "Value has been removed from the list." );
	#endif
	*this->lst = NULL;
}